#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
/**
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，
 * 并且每种组合中不存在重复的数字。
 * 说明：
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * 
 */
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> slice;
    void dfs(int cur, int sum, int k, int n)
    {
        if (k <= 0)
        {
            if (sum == n)
                ans.push_back(slice);
            return;
        }
        if (sum > n)
            return;
        for (int i = cur + 1; i <= 9; ++i)
        {
            slice.push_back(i);
            dfs(i, sum + i, k - 1, n);
            slice.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n)
    {
        dfs(0, 0, k, n);
        return ans;
    }
};
